class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        n, m = len(nums1), len(nums2)
        # 构建小顶堆，因为python的堆不支持自定义排序函数
        # 因此存储的是元素和+索引对。直接根据元素和进行排序
        pq = []

        for i in range(n):
            heapq.heappush(pq, (nums1[i]+ nums2[0], i, 0))
        
        res = []
        for i in range(k):
            # 每次获取堆顶索引对，添加到结果数组
            _, i1, i2 = heapq.heappop(pq)
            res.append([nums1[i1], nums2[i2]])
            # 将下一个合法的索引对加入堆，索引对编号 = i1 * m + i2
            if i2 + 1 < m:
                heapq.heappush(pq, (nums1[i1] + nums2[i2 + 1], i1, i2 + 1))
        return res